package heap_1101;


// 使用小堆来维护
// 对象的正确性检查
// size >= 0
// array != null
// array + size 满足小堆的性质
// 堆的定义：要求每个位置都比它的两个孩子（如果存在的话）要小
public class MyPriorityQueuePrimitiveType {
    // 元素类型使用 long 类型
    // 暂时不考虑扩容的情况
    private final long[] array = new long[1000];
    private int size;       // 元素的个数

    private static void assertTrue(boolean condition, String message) {
        if (!condition) {
            throw new RuntimeException(message);
        }
    }

    public void 优先级对象的正确检查() {
        assertTrue(size >= 0, "size 必须大于等于 0");
        assertTrue(size <= 1000, "size 必须小于等于容量（1000）");
        assertTrue(array != null, "array 必须有数组");
        assert小堆(array, size);
    }

    private static void assert小堆(long[] array, int size) {
        for (int i = 0; i < size; i++) {    // 理论上只需要检查有孩子的
            if (2 * i + 1 < size) {
                // 说明有左孩子
                assertTrue(array[i] <= array[2 * i + 1], "我的值必须比我的左孩子的值小");
            }

            if (2 * i + 2 < size) {
                // 说明有右孩子
                assertTrue(array[i] <= array[2 * i + 2], "我的值必须比我的右孩子的值小");
            }
        }
    }

    public MyPriorityQueuePrimitiveType() {
        // 空的优先级队列
        size = 0;
        优先级对象的正确检查();
    }

    // 查看优先级队列中最小值
    // O(1)
    public long peek() {
        if (size <= 0) {
            throw new RuntimeException("空的");
        }

        return array[0];    // 根的位置就是最小值
    }

    // 把 e 添加到堆中（优先级队列）
    // 同时维护好最小堆的性质
    // 最坏情况：从叶子 -> 根
    // O(log(n))
    public void offer(long e) {
        array[size] = e;
        size++;

        int index = size - 1;
        while (index != 0) {    // index == 0 说明是根，不需要调整了
            // 求双亲的下标
            int pIdx = (index - 1) / 2;
            // 比较要调整的位置和双亲的大小
            if (array[pIdx] <= array[index]) {
                break;
            }

            // 交换
            swap(array, pIdx, index);

            // 继续双亲位置调整
            index = pIdx;
        }


        优先级对象的正确检查();
    }

    // 删除堆顶元素
    // 同时维护好最小堆的性质
    // O(log(n))
    public long poll() {
        if (size <= 0) {
            throw new RuntimeException("空的");
        }

        long e = array[0];

        array[0] = array[size - 1];
        array[size - 1] = 0;    // 没有意义，只是为了调试好看
        size--;

        adjustDown小堆(0);    // O(log(n))

        优先级对象的正确检查();

        return e;
    }

    public void adjustDown小堆(int index) {
        while (2 * index + 1 < size) {  // 说明不是叶子
            // 找到最小的孩子
            int minIdx = 2 * index + 1;
            if (minIdx + 1 < size && array[minIdx + 1] < array[minIdx]) {
                minIdx++;
            }

            // 判断 "我" 和最小孩子的关系
            if (array[index] <= array[minIdx]) {
                return;
            }

            // 交换
            swap(array, index, minIdx);
            // 以最小孩子的位置再次这个过程
            index = minIdx;
        }
    }
    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static void main(String[] args) {
        MyPriorityQueue q = new MyPriorityQueue();

        q.offer(3);
        q.offer(9);
        q.offer(7);
        q.offer(2);
        q.offer(6);
        q.offer(8);
        q.offer(5);
        q.offer(4);
        q.offer(3);

        System.out.println(q.poll());   // 2
        q.offer(1);
        System.out.println(q.poll());   // 1
        q.offer(1);
        q.offer(0);
        System.out.println(q.poll());   // 0
        System.out.println(q.poll());   // 1
    }
}
